﻿using System;

class SequenceOfMaximalSum

            // Write a program that finds the sequence of maximal sum in given array. Example:
	        // {2, 3, -6, -1, 2, -1, 6, 4, -8, 8}  {2, -1, 6, 4}

{
    static void Main()
    {
        Console.Write("Enter the length of the array:");
        int arraySize = int.Parse(Console.ReadLine());
        int[] array = new int[arraySize];
        Console.WriteLine();

        Console.WriteLine("Enter the elemetns of the array:");
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = int.Parse(Console.ReadLine());
        }

        int max = array[0];
        int maxEnd = array[0];
        int bestSeq = 1; 
        int currentSeq = 1;
        int start = 0;
        int startTemp = 0;
        for (int i = 1; i < array.Length; ++i)
        {
            if (array[i] + maxEnd > array[i])
            {
                maxEnd = array[i] + maxEnd;
                currentSeq++;
            }
            else
            {
                maxEnd = array[i];
                startTemp = i;
                currentSeq = 1;
            }
            if (maxEnd > max)
            {
                max = maxEnd;
                bestSeq = currentSeq;
                start = startTemp;
            }
        }
        Console.WriteLine();

        Console.WriteLine("The sequence with the maximal sum is:");
        for (int i = start; i < start + bestSeq; ++i)
        {
            Console.Write("{0} ", array[i]);
        }
        Console.WriteLine();
    }
}
